﻿// 0826train04.cpp : 此文件包含 "main" 函数。程序执行将在此处开始并结束。
//

#include <iostream>
#include <string>
#include <sstream>
#include <vector>
#include <algorithm>
#include <limits>
#include <deque>
#include <unordered_map>
#include <unordered_set>
#include <bitset>

using namespace std;

/*
租用公共双人自行车，每辆自行车最多坐两人，最大载重M
给出部门每个人的体重，请问最少需要租用多少双人自行车

输入描述
第一行两个数字m、n，分别代表自行车限重，部门总人数
第二行，n个数字，代表每个人的体重，体重都小于等于自行车限重m
0<m<=200
0<n<=1000000

输出描述
最小需要的双人自行车数量

输入
3 4
3 2 2 1

输出
3
输入
3 m自行车限重 4部门总人数
3 2 2 1
 */
class Solution01
{
public:
    Solution01(int limit, vector<int>&nums)
    {
        sort(nums.begin(), nums.end());
        int result = 0;
        int left = 0, right = nums.size() - 1;

        while (left<=right)
        {
            if (left==right)
            {
                result += 1;
                break;
            }

            if (nums[left]+nums[right]<=limit)
            {
                result += 1;
                left++;
                right--;
            }
            else
            {
                result += 1;
                right--;
            }

        }
        cout << result;
        //Solution01
    }

};

/*
 题目描述
求出大于或等于 N 的最小回文素数
如果一个数大于 1，且其因数只有 1 和它自身，那么这个数是素数
例如，2，3，5，7，11 以及 13 是素数
如果一个数从左往右读与从右往左读是一样的，那么这个数是回文数，例如，12321 是回文数

输入描述
一个数

输出描述
一个数

示例1
输入
6
输出
7
 */

class Solution02
{
public:
    int isPrime(int num)
    {
        if (num == 1)return false;
        if (num%2==0)
        {
            return num == 2;
        }
        for (int i=3; i*i<=num; i++)
        {
            if (num % i == 0) return false;
        }
        return true;
    }

    int generatePalindrome(int left)
    {
        int palindrome = left;
        left = left / 10;
        while (left!=0)
        {
            palindrome = palindrome * 10 + left % 10;
            left = left / 10;
        }
        return palindrome;
    }

    Solution02(int num)
    {
        solve02(num);
    }

    void solve02(int num)
    {
        if (num <= 11)
        {
            for (int i = num; i <= 11; i++)
            {
                if (isPrime(i))
                {
                    cout << i;
                    return;
                }

            }
        }

        
        for (int left=10; left<=num; left++)
        {
            int min_palin = generatePalindrome(left);
            if (min_palin>=num && isPrime(min_palin))
            {
                cout << min_palin;
                return;
            }
        }

    }
};


/*
 存在一种虚拟IPv4地址，
 由4小节组成，
 除了第一小节的范围是1-128以外，其余三节的范围为0-255，以#号间隔，格式如下：
(1~128)#(0~255)#(0~255)#(0~255)

例如：
128#0#255#255，转换为32位整数的结果为2147549183（0x8000ffff）
1#0#0#0，转换为32位整数的结果为16777216（0x01000000）
请利用这个特性把虚拟IPv4地址转换为一个32位的整数，IPv4地址以字符串形式给出，
要求每个IPvV4地址只能对应到唯一的整数上
如果是非法IPv4，输出字符串"invalid IP"

输入描述
输入一行，虚拟IPv4地址格式字符串
输出描述
输出一行，按照要求输出整型或者特定字符

输入
100#101#1#5
输出
1684340997

 */
class Solution03
{
public:
    bool isNum(string&oh_str)
    {
        for (auto&oh_char:oh_str)
        {
            bool is_num = oh_char >= '0' && oh_char <= '9';
            if (!is_num) return false;
        }
        return true;
    }

    bool checkVerify(string&ipv4_str)
    {
        //(1~128)#(0~255)#(0~255)#(0~255)
        stringstream oh_sstream(ipv4_str);
        string token;
        while (getline(oh_sstream, token, '#'))
        {
            str_vec.push_back(token);
        }

        if (str_vec.size() != 4) return false;

        for (int i=0; i<str_vec.size(); i++)
        {
            if (!isNum(str_vec[i])) return false;

            //1-128
	        if (i==0)
	        {
                if (stoi(str_vec[0]) < 1 || stoi(str_vec[0]) > 128)
                    return false;
	        }
            else
            {
            	//0~255
                if (stoi(str_vec[i]) < 0 || stoi(str_vec[i]) > 255)
                    return false;
            }
        }
        return true;
        //checkVerify
    }
    Solution03(string&ipv4_str)
    {
        if (!checkVerify(ipv4_str))
        {
            cout << "invalid IP";
            return;
        }

        //数字转16进制hex
        vector<string>hex_vec;
        for (int i=0; i<str_vec.size();i++)
        {
            stringstream hex_sstream;
            hex_sstream << hex << stol(str_vec[i]);
            string hex_str = hex_sstream.str();
            if (hex_str.size()<2)
            {
                hex_str = '0' + hex_str;
            }
            hex_vec.push_back(hex_str);
        }

        stringstream total_hex_sstream;
        for (auto&hex_str:hex_vec)
        {
            total_hex_sstream << hex_str;
        }

        string total_hex_str = total_hex_sstream.str();
        cout << stol(total_hex_str, nullptr, 16);

    }
private:
    vector<string>str_vec;
};

int main()
{
    {
        //二进制转换
        //"10101010"
        string bin_str = "10101010";
        bitset<8> bs(bin_str);
        unsigned long num = bs.to_ulong();
        cout << num << endl;

        bitset<8>bs2(170);
        cout << bs2.to_string();

        return 0;
    }
	{
        int num = 255;
        stringstream hex_stream;
        //10转16
        hex_stream << hex << num;
        cout << hex_stream.str() << endl;
        //16转10
        cout << stol(hex_stream.str(), nullptr, 16);
        return 0;
	}
    {

        //100#101#1#5
        //1684340997
        string input;
        cin >> input;
        //string input = "100#101#1#";
        Solution03 solu(input);
        
        return 0;
    }
	{
        //int num;
        //cin >> num;
        int num = 701275;
        Solution02 solu(num);
        //cout << '\n';
        //cout << solu.isPrime(1011101);

        return 0;
	}
    int limit, vec_size;
    cin >> limit >> vec_size;

    vector<int>nums(vec_size);
    for (int i=0; i<vec_size; i++)
    {
        cin >> nums[i];
    }

    Solution01 solu(limit, nums);
}

// 运行程序: Ctrl + F5 或调试 >“开始执行(不调试)”菜单
// 调试程序: F5 或调试 >“开始调试”菜单

// 入门使用技巧: 
//   1. 使用解决方案资源管理器窗口添加/管理文件
//   2. 使用团队资源管理器窗口连接到源代码管理
//   3. 使用输出窗口查看生成输出和其他消息
//   4. 使用错误列表窗口查看错误
//   5. 转到“项目”>“添加新项”以创建新的代码文件，或转到“项目”>“添加现有项”以将现有代码文件添加到项目
//   6. 将来，若要再次打开此项目，请转到“文件”>“打开”>“项目”并选择 .sln 文件
